package 排序.选择排序;

public class SelectSort {
    /**
     * 排序.选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void SelectSort2(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right){
            int i=left+1;
            int MinIndex=left;
            int MaxIndex=left;
            while(i<=right){

                if(array[i]>array[MaxIndex]){
                    MaxIndex=i;
                }

                if(array[i]<array[MinIndex]){
                    MinIndex=i;
                }

                i++;

            }
            if(MaxIndex==left){
                MaxIndex=MinIndex;
            }
            swap(array,left,MinIndex);
            swap(array,right,MaxIndex);
            left++;
            right--;
        }
    }
    public static void selectSort(int[] array){
        int minIndex=0;//最小值下标
        for(int i=0;i<array.length-1;i++){
            minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,minIndex,i);
        }
    }
    public static void swap(int[] array,int min,int i){
        int temp=array[min];
        array[min]=array[i];
        array[i]=temp;
    }
}
